package com.javaDemo.ti;

import java.util.HashMap;
import java.util.Map;

/**
 * 两数之和查找器
 * 
 * @ClassName: FindTwoNumberSum (原 BianLiyicizhaochuxiiangjia)
 * @Author: csy
 * @Date: 2021/3/17 09:52
 * @Description: 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数的下标
 *               解题思路：
 *               1. 使用HashMap存储遍历过的数字及其下标
 *               2. 对于每个当前数字，检查目标值减去当前数字的结果是否在HashMap中
 *               3. 如果存在，则找到了答案；如果不存在，将当前数字及其下标存入HashMap
 *               时间复杂度：O(n)，空间复杂度：O(n)
 */
public class FindTwoNumberSum {
    // 测试用的示例数组
    private static final Integer[] NUMBERS = { 1, 2, 2, 1, 4, 5 };

    public static void main(String[] args) {
        int targetSum = 7;
        int[] result = findTwoSumIndices(targetSum);
        if (result.length == 2) {
            System.out.printf("找到和为 %d 的两个数的下标：[%d, %d]%n",
                    targetSum, result[0], result[1]);
            System.out.printf("对应的数字是：%d 和 %d%n",
                    NUMBERS[result[0]], NUMBERS[result[1]]);
        } else {
            System.out.printf("未找到和为 %d 的两个数%n", targetSum);
        }
    }

    /**
     * 查找数组中和为目标值的两个数的下标
     * 
     * @param target 目标和
     * @return 包含两个数字下标的数组，如果未找到则返回空数组
     */
    private static int[] findTwoSumIndices(int target) {
        // 使用HashMap存储遍历过的数字和它们的下标
        Map<Integer, Integer> numIndexMap = new HashMap<>();

        // 遍历数组
        for (int i = 0; i < NUMBERS.length; i++) {
            // 计算需要查找的补数
            int complement = target - NUMBERS[i];

            // 如果补数存在于HashMap中，说明找到了答案
            if (numIndexMap.containsKey(complement)) {
                return new int[] { numIndexMap.get(complement), i };
            }

            // 将当前数字及其下标存入HashMap
            numIndexMap.put(NUMBERS[i], i);
        }

        // 未找到符合条件的两个数
        return new int[0];
    }
}
